#include<iostream>
using namespace std;

  struct ListNode {
      int val;
      ListNode *next;
      ListNode(int x) : val(x), next(NULL) {}
  };
 
class Solution {
public:
    ListNode* getIntersectionNode(ListNode* head1, ListNode* head2) {
        ListNode* cur1 = head1, * cur2 = head2;
        int cnt1 = 0, cnt2 = 0;
        while (cur1) {
            cur1 = cur1->next;
            cnt1++;
        }
        while (cur2) {
            cur2 = cur2->next;
            cnt2++;
        }
        int gap = cnt2 - cnt1;
        cur1 = head1, cur2 = head2;
        if (gap < 0) {
            gap = -gap;
            while (gap--)cur1 = cur1->next;
        }
        else while (gap--)cur2 = cur2->next;

        while (cur1 && cur2) {
            if (cur1 == cur2)return cur1;
            cur1 = cur1->next;
            cur2 = cur2->next;
        }
        return nullptr;
    }
};